#include <string>

class TrieNode{
public:
    char data;
    bool isEndChar;
    TrieNode *children[26];
    TrieNode(char data){
        this->data = data;
        isEndChar = false;
        for(int i=0;i<26;i++){
            children[i] = nullptr;
        }
    }
};

class Trie
{
private:
    TrieNode *root;
public:
    Trie(/* args */);
    ~Trie();
    void insert(string word);
    bool search(string word);
};

Trie::Trie(/* args */)
{
    root = new TrieNode('/');
}

Trie::~Trie()
{
}

void Trie::insert(string word)
{ 
    TrieNode *curr = root;
    for(int i=0;i<word.length();i++){
        int index = word[i] - 'a';
        if(curr->children[index] == nullptr){
            curr->children[index] = new TrieNode(word[i]);
        } 
        curr = curr->children[index];
    }
    curr->isEndChar = true;
}

bool Trie::search(string word)
{
    TrieNode *curr = root;
    for (int i = 0; i < word.length(); i++)
    {
        int index = word[i] - 'a';
        if(curr->children[index] == nullptr){
            return false;
        }
        curr = curr->children[index];
    }
    if (curr->isEndChar) return true;
    else return false;
}